{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Neural Networks - Part 1\n",
    "\n",
    "2016-06-17, Josh Montague\n",
    "\n",
    "Motivation, a little history, a naive implementation, and a discussion of neural networks.\n",
    "\n",
    "\n",
    "## Logistic regression\n",
    "\n",
    "Recap of the structural pillars of logistic regression for classification ([previous RST](https://github.com/DrSkippy/Data-Science-45min-Intros/blob/master/logistic-regression-101/Logistic%20Regression.ipynb)).\n",
    "\n",
    "<img src=\"img/NN-1.jpeg\">    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see an example where logistic regression works. Consider some two-dimensional data that we'd like to classify. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "from mlxtend.evaluate import plot_decision_regions\n",
    "from sklearn.datasets import make_blobs\n",
    "from sklearn.linear_model import LogisticRegression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "samples = 20\n",
    "\n",
    "X, y = make_blobs(n_samples=samples, n_features=2, cluster_std=0.25,\n",
    "                  centers=[(0, 0.5), (1.5, 0.5)], shuffle=False, random_state=1)\n",
    "\n",
    "# fit the LR model\n",
    "clf = LogisticRegression().fit(X,y)\n",
    "\n",
    "# plotting decision regions\n",
    "plot_decision_regions(X, y, clf=clf, res=0.02)\n",
    "plt.xlabel('x1'); plt.ylabel('x2'); plt.title('LR (linearly separable)')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print('The model features are weighted according to: {}'.format(clf.coef_))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A different view of logistic regression \n",
    "\n",
    "Consider a schematic reframing of the LR model above. This time we'll treat the inputs as nodes, and they connect to other nodes via vertices that represent the weight coefficients.\n",
    "\n",
    "<img src=\"img/NN-2.jpeg\">   \n",
    "\n",
    "The diagram above is a (simplified form of a) single-neuron model in biology. \n",
    "\n",
    "<img src=\"img/neuron.gif\">   \n",
    "\n",
    "As a result, this is the same model that is used to demonstrate a computational neural network. \n",
    "\n",
    "So that's great. Logistic regression works, why do we need something like a neural network? To start, consider an example where the LR model breaks down:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "rng = np.random.RandomState(1)\n",
    "X = rng.randn(samples, 2)\n",
    "y = np.array(np.logical_xor(X[:, 0] > 0, X[:, 1] > 0), dtype=int)\n",
    "\n",
    "clf = LogisticRegression().fit(X,y)\n",
    "\n",
    "plot_decision_regions(X=X, y=y, clf=clf, res=0.02, legend=2)\n",
    "plt.xlabel('x1'); plt.ylabel('x2'); plt.title('LR (XOR)')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why does this matter? Well...\n",
    "\n",
    "\n",
    "## Neural Networks\n",
    "\n",
    "### Some history\n",
    "\n",
    "In the 1960s, when the concept of neural networks were first gaining steam, this type of data was a show-stopper. In particular, the reason our model fails to be effective with this data is that it's not linearly separable; it has interaction terms.\n",
    "\n",
    "This is a specific type of data that is representative of an XOR logic gate. It's not magic, just well-known, and a fundamental type of logic in computing. We can say it in words, as approximately: \"label is 1, if either x1 or x2 is 1, but not if both are 1.\"\n",
    "\n",
    "At the time, this led to an interesting split in computational work in the field: on the one hand, some people set off on efforts to **design very custom data and feature engineering tactics so that existing models would still work.** On the other hand, people set out to solve the challenge of **designing new algorithms**; for example, this is approximately the era when the support vector machine was developed. Since progress on neural network models slowed significantly in this era (rememeber that computers were entire rooms!), this is often referred to as the first \"AI winter.\" Even though the multi-layer network was designed a few years later, and solved the XOR problem, the attention on the field of AI and neural networks had faded. \n",
    "\n",
    "Today, you might (sensibly) suggest something like an 'rbf-kernel SVM' to solve this problem, and that would totally work! But that's not where we're going today. \n",
    "\n",
    "With the acceleration of computational power in the last decade, there has been a resurgence in the interest (and capability) of neural network computation.\n",
    "\n",
    "### So what does a neural network look like?\n",
    "\n",
    "What is a multi-layer model, and how does it help solve this problem? **Non-linearity and feature mixing leads to *new* features that we don't have to encode by hand.** In particular, we no longer depend just on combinations of input features. We combine input features, apply non-linearities, then combine all of those as *new* features, apply *additional* non-linearities, and so on until basically forever. \n",
    "\n",
    "It sounds like a mess, and it pretty much can be. But first, we'll start simply. Imagine that we put just a single layer of \"neurons\" between our input data and output. How would that change the evaluation approach we looked at earlier?\n",
    "\n",
    "<img src=\"img/NN-3.jpeg\">   \n",
    "\n",
    "\n",
    "### DIY neural network!\n",
    "\n",
    "**Reminder:** manually writing out algorithms is a terrible idea for using them, but a great idea for learning how they work.\n",
    "\n",
    "To get a sense for how the diagram above works, let's first write out the \"single-layer\" version (which we saw above  is equivalent to logistic regression and doesn't work!). We just want to see how it looks in the form of forward- and backward-propagation.\n",
    "\n",
    "Remember, we have a (``samples x 2``) input matrix, so we need a ``(2x1)`` matrix of weights. And to save space, we won't use the fully-accurate and correct implementation of backprop and SGD; instead, we'll use a simplified version that's easier to read but has very similar results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# make the same data as above (just a little closer so it's easier to find)\n",
    "rng = np.random.RandomState(1)\n",
    "X = rng.randn(samples, 2)\n",
    "\n",
    "y = np.array(np.logical_xor(X[:, 0] > 0, X[:, 1] > 0), dtype=int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def activate(x, deriv=False):\n",
    "    \"\"\"sigmoid activation function and its derivative wrt the argument\"\"\"\n",
    "    if deriv is True:\n",
    "        return x*(1-x)\n",
    "    return 1/(1+np.exp(-x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# initialize synapse0 weights randomly with mean 0\n",
    "syn0 = 2*np.random.random((2,1)) - 1\n",
    "\n",
    "# nothing to see here... just some numpy vector hijinks for the next code\n",
    "y = y[None].T"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is the iterative phase. We propagate the input data forward through the synapse (weights), calculate the errors, and then back-propogate those errors through the synapses (weights) according to the proper gradients. Note that the number of iterations is arbitary at this point. We'll come back to that. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i in range(10000):\n",
    "    # first \"layer\" is the input data\n",
    "    l0 = X\n",
    "    \n",
    "    # forward propagation\n",
    "    l1 = activate(np.dot(l0, syn0))\n",
    "\n",
    "    ### \n",
    "    # this is an oversimplified version of backprop + gradient descent\n",
    "    #\n",
    "    # how much did we miss?\n",
    "    l1_error = y - l1\n",
    "    #\n",
    "    # how much should we scale the adjustments?\n",
    "    # (how much we missed by) * (gradient at l1 value)\n",
    "    # ~an \"error-weighted derivative\"\n",
    "    l1_delta = l1_error * activate(l1,True)\n",
    "    ###\n",
    "    \n",
    "    # how much should we update the weight matrix (synapse)? \n",
    "    syn0 += np.dot(l0.T,l1_delta)\n",
    "    \n",
    "    # some insight into the update progress\n",
    "    if (i% 2000) == 0:\n",
    "        print(\"Mean error @ iteration {}: {}\".format(i, np.mean(np.abs(l1_error))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, this basically didn't work at all! \n",
    "\n",
    "Even though we aren't looking at the actual output data, we can use it to look at the accuracy; it never got much better than random guessing. Even after thousands of iterations! But remember, we knew that would be the case, because this single-layer network is functionally the same as vanilla logistic regression, which we saw fail on the xor data above! \n",
    "\n",
    "But, now that we have the framework and understanding for how to optimize backprogation, we can **add an additional layer to the network (a so-called \"hidden\" layer of neurons),** which will introduce the kind of mixing we need to represent this data.\n",
    "\n",
    "As we saw above in the diagram (and talked about), introduction of a new layer means that we get an extra step in both the forward- and backward-propagation steps. This new step means we need an additional weight (synapse) matrix, and an additional derivative calculation. Other than that, the code looks pretty much the same."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### fall-back data ####\n",
    "# convert to/from raw nbconvert\n",
    "X = np.array([[0,0],\n",
    "            [0,1],\n",
    "            [1,0],\n",
    "            [1,1]])\n",
    "\n",
    "                \n",
    "y = np.array([[0, 1, 1, 0]]).T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# hold tight, we'll come back to choosing this number\n",
    "hidden_layer_width = 3\n",
    "\n",
    "# initialize synapse (weight) matrices randomly with mean 0\n",
    "syn0 = 2*np.random.random((2,hidden_layer_width)) - 1\n",
    "syn1 = 2*np.random.random((hidden_layer_width,1)) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i in range(60000):\n",
    "\n",
    "    # forward propagation through layers 0, 1, and 2\n",
    "    l0 = X\n",
    "    l1 = activate(np.dot(l0,syn0))\n",
    "    l2 = activate(np.dot(l1,syn1))\n",
    "\n",
    "    # how much did we miss the final target value?\n",
    "    l2_error = y - l2\n",
    "      \n",
    "    # how much should we scale the adjustments?\n",
    "    l2_delta = l2_error*activate(l2,deriv=True)\n",
    "\n",
    "    # project l2 error back onto l1 values according to weights\n",
    "    l1_error = l2_delta.dot(syn1.T)\n",
    "    \n",
    "    # how much should we scale the adjustments?\n",
    "    l1_delta = l1_error * activate(l1,deriv=True)\n",
    "\n",
    "    # how much should we update the weight matrices (synapses)? \n",
    "    syn1 += l1.T.dot(l2_delta)\n",
    "    syn0 += l0.T.dot(l1_delta)\n",
    "    \n",
    "    if (i % 10000) == 0:\n",
    "        print(\"Error @ iteration {}: {}\".format(i, np.mean(np.abs(l2_error))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, this time we started at random guessing (sensible), but notice that we quickly reduced our overall error! That's excellent!\n",
    "\n",
    "**Note:** I didn't have time to debug the case where the full XOR data only trained to label one quadrant correctly. To get a sense for how it can look with a smaller set, change the \"fall-back data\" cell to code, and run the cells starting there!\n",
    "\n",
    "Knowing that the error is lower is great, but we can also inspect the results of the fit network by looking at the forward propagation results from the trained synapses (weights)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def forward_prop(X):\n",
    "    \"\"\"forward-propagate data X through the pre-fit network\"\"\"\n",
    "    l1 = activate(np.dot(X,syn0))\n",
    "    l2 = activate(np.dot(l1,syn1))\n",
    "    return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# numpy and plotting shenanigans come from:\n",
    "# http://scikit-learn.org/stable/auto_examples/svm/plot_iris.html\n",
    "\n",
    "# mesh step size\n",
    "h = .02  \n",
    "\n",
    "# create a mesh to plot in\n",
    "x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1\n",
    "y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1\n",
    "xx, yy = np.meshgrid(np.arange(x_min, x_max, h),\n",
    "                     np.arange(y_min, y_max, h))\n",
    "\n",
    "# calculate the surface (by forward-propagating)\n",
    "Z = forward_prop(np.c_[xx.ravel(), yy.ravel()])\n",
    "\n",
    "# reshape the result into a grid\n",
    "Z = Z.reshape(xx.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plt.contourf(xx, yy, Z, cmap=plt.cm.Paired, alpha=0.8)\n",
    "\n",
    "# we can use this to inspect the smaller dataset\n",
    "#plt.plot(X[:, 0], X[:, 1], 'o')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Success! (Possibly... depending on whether Josh debugged the larger network problem :) ). If only one quadrant was trained correctly, go use the smaller dataset!\n",
    "\n",
    "\n",
    "# Wrap-up\n",
    "\n",
    "The stuff in this session is just a very basic start! The limits to the increasing complexity are now at the hardware level! Networks can be amazingly complicated, too. Below is an example from a talk I saw - note how interestingly the layers are *building* on each other to represent increasingly complicated structure in the context of facial recognition. \n",
    "\n",
    "<img src=\"img/3l-face.png\">  \n",
    "\n",
    "It's not clear how you'd encode \"this is a face,\" but once you see how the first layer's \"atomic\" components are assembled into abstract *parts* of a face, and how those *parts* are combined into representations of kinds of faces, it seems more believable!\n",
    "\n",
    "## Don't actually do it like this\n",
    "\n",
    "And, as you probably guessed, what we've done above isn't how you use these in practice. There are many Python libraries for building and using various neural network models. And, as you might expect, many are built with an object-oriented expressiveness:\n",
    "\n",
    "```python\n",
    "# pseudo-code (that is actually very nearly valid)\n",
    "nn = Network(optimizer='sgd')\n",
    "nn.add_layer('fully_connected', name='l0', nodes=4)\n",
    "nn.add_layer('fully_connected', name='l1', nodes=5)\n",
    "nn.add_layer('fully_connected', name='l2', nodes=2)\n",
    "nn.compile()\n",
    "nn.fit(X,y)\n",
    "```\n",
    "\n",
    "In Neural Networks - Part 2, we'll look at some of these libraries and use them for some learning tasks! (*hold me to it!*)\n",
    "\n",
    "In addition to using optimized libraries, there are many other issues and topics that go into developing and using neural networks for practical purposes. Below is a bag-of-words approach to some terms and phrases that you'll invariably see when reading about neural networks.\n",
    "\n",
    "\n",
    "## Neural Network Word Salad\n",
    "\n",
    "- GPU (graphical processing unit)\n",
    "    - The matrix manipulations needed for large network training are typically bottlenecked by the compute throughput of a CPU. Starting in ~2013, people figured out the computer graphics chips were much faster at computing these steps and are now the go-to hardware for training networks. CPUs still work! They just tend to be an order of magnitude slower.\n",
    "\n",
    "- architecture\n",
    "    - We only looked at so-called \"fully-connected\" networks - that is, every node was connected to every other node downstream. This is not the only way to design the layout! \n",
    "    - Among many others, so-called \"convolution networks\" are very common in image recognition tasks; each layer combines a *region* of the previous layer's outputs into a single node in the subsequent layer.\n",
    "    - There are still other choices to be made in designing a network: the number of nodes in a hidden layer, the activation function, and more. \n",
    "\n",
    "- batching\n",
    "    - If you're training a network on the entirety of the internet's search queries, you can't exactly feed it all forward and backward through the network at once. The concept of batching is deciding how much of the input data to feed forward (and backward) before updating your weight matrices.\n",
    "\n",
    "- training epochs\n",
    "    - the magic numbers in our ``for`` loops above were chosen arbitrarily. A lot of work has also gone into deciding how to optimize the convergence of network training. \n",
    "\n",
    "- regularization\n",
    "    - Neural networks, too, can suffer from overfitting. There are tactics to \n",
    "    - \"dropout\"\n",
    "    - \"pooling\"\n",
    "    \n",
    "- \"deep learning\"\n",
    "    - lots of layers\n",
    "    \n",
    "    \n",
    "## Links\n",
    "\n",
    "To save you some time if you want to learn more, here are some of the references that I found the most helpful while researching for this RST:\n",
    "\n",
    "- [Hacker's guide to Neural Networks](http://karpathy.github.io/neuralnets/)\n",
    "- [Deep Learning Basics: Neural Networks, Backpropagation and Stochastic Gradient Descent](http://alexminnaar.com/deep-learning-basics-neural-networks-backpropagation-and-stochastic-gradient-descent.html)\n",
    "- [A Neural Network in 11 lines of Python](http://iamtrask.github.io/2015/07/12/basic-python-network/)\n",
    "- [A Neural Network in 13 lines of Python](http://iamtrask.github.io/2015/07/27/python-network-part2/)\n",
    "- [Intro to Neural Networks](http://www.slideshare.net/DeanWyatte/intro-to-neural-networks)\n",
    "- [Single-Layer Neural Networks and Gradient Descent](http://sebastianraschka.com/Articles/2015_singlelayer_neurons.html)\n",
    "- [Tensorflow Playground](http://playground.tensorflow.org)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
